package com.xzx.simple;

import org.junit.Test;

/**
 * @className com.xzx.simple algorithm
 * @description: 最长公共前缀
 * @author: xzx
 * @date: 19-3-25 15:03
 * @version: v1
 */
public class LongestCommonPrefix {
    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {

        return null;
    }
    /**
     * 解析
     * 大概有这五种思路, 一般都会采用第四种, 但是耗时太多
     *
     * 1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准，把它的前缀串，与其他所有字符串进行判断，看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。
     *
     * 2、列出所有的字符串的前缀子串，将它们合并后排序，找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))
     *
     * 3、纵向扫描：从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。
     *
     * 4、横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。
     *
     * 5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。
     */

    /**
     * 提交时间	状态	执行用时	内存消耗	语言
     * 5 小时前	通过	13 ms	40.5 MB	java
     * 5 小时前	通过	13 ms	37.2 MB	java
     * @param strs
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs.length == 1){
            return strs[0];
        }
        StringBuilder sb = new StringBuilder();
        if (strs.length>1) {
            int len = strs[0].length();
            for (int i = 0; i < len; i++) {
                char curr = strs[0].charAt(i);
                for (int j = 1; j < strs.length; j++) {
                    if (strs[j].length()<=i ||strs[j].charAt(i) != curr) {
                        return sb.toString();
                    }
                    if (strs[j].charAt(i) == curr && j == strs.length - 1) {
                        sb.append(curr);
                    }
                }
            }
        }
        return sb.toString();
    }

    /**
     * 尝试的方法，用过String.split方法，判断指定字符的出现次数
     * 提交时间	状态	执行用时	内存消耗	语言
     * 3 天前	通过	87 ms	50 MB	java
     * 3 天前	通过	69 ms	39.3 MB	java
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {
        if(strs.length <= 1){
            return  strs.length == 1 ? strs[0] : "";
        }
        String result = "";
        StringBuilder builder = new StringBuilder();
        for (String s : strs){
            builder.append("," + s);
        }
        builder.append(",");
        char[] pop = strs[0].toCharArray();
        String str4 = builder.toString();
        String num = "";
        for (char p: pop ) {
            num = num + p;
            if (str4.split("," + num).length > strs.length){
                result = num;
            }
        }
        return result;
    }

    /**
     * 官方解法之一，
     * 提交时间	状态	执行用时	内存消耗	语言
     * 几秒前	通过	10 ms	38.1 MB	java
     * @param strs
     * @return
     */
    public String longestCommonPrefix3(String[] strs) {
        if (strs.length <= 1){
            return strs.length  == 0 ? "" : strs[0];
        }
        String result = strs[0];
        for (int i = 1; i < strs.length; i++){
            while (strs[i].indexOf(result) != 0){
                result = result.substring(0,result.length() - 1);
            }
        }
        return result;
    }

    /**
     * 提交时间	状态	执行用时	内存消耗	语言
     * 几秒前	通过	11 ms	39.8 MB	java
     * @param strs
     * @return
     */
    public String longestCommonPrefix4(String[] strs) {
        if (strs.length <= 1){
            return strs.length  == 0 ? "" : strs[0];
        }
        for (int i = 0; i < strs[0].length() ; i++){
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j ++) {
                if(i == strs[j].length() || strs[j].charAt(i) != c){
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    /**
     * 分治
     * 提交时间	状态	执行用时	内存消耗	语言
     * 几秒前	通过	10 ms	37.6 MB	java
     * @param strs
     * @return
     */
    public String longestCommonPrefix5(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        return longestCommonPrefix(strs, 0 , strs.length - 1);
    }

    private String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        }
        else {
            int mid = (l + r)/2;
            String lcpLeft =   longestCommonPrefix(strs, l , mid);
            String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    String commonPrefix(String left,String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if( left.charAt(i) != right.charAt(i) ){
                return left.substring(0, i);
            }
        }
        return left.substring(0, min);
    }

    /**
     * 二分
     * 几秒前	通过	10 ms	38.5 MB	java
     * @param strs
     * @return
     */
    public String longestCommonPrefix6(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        }
        int minLen = Integer.MAX_VALUE;
        for(String str : strs){
            minLen = Math.min(minLen, str.length());
        }
        int low = 1;
        int high = minLen;
        while (low <= high) {
            int middle = (low + high) / 2;
            if(isCommonPrefix(strs, middle)){
                low = middle + 1;
            }
            else{
                high = middle - 1;
            }
        }
        return strs[0].substring(0, (low + high) / 2);
    }

    private boolean isCommonPrefix(String[] strs, int len){
        String str1 = strs[0].substring(0,len);
        for (int i = 1; i < strs.length; i++){
            if(!strs[i].startsWith(str1)){
                return false;
            }

        }
        return true;
    }

    @Test
    public void test(){
        long start = System.currentTimeMillis();
        String[] li = {"flower","flow","flight"};
        String re = longestCommonPrefix3(li);
        long end = System.currentTimeMillis();
        System.out.println("返回值为：{"+re+"}，耗时为：{"+end+"}"+start);
    }
}
